package DataStuctures.BST;

public class BST<E extends Comparable<E>> {
    //类型E要具有可比较性

    private class Node{
        public E e;
        public Node left,right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    //向二分搜索树中添加新的元素
    public void add(E e){
        if(root == null) {
            root = new Node(e);
            size ++;
        }else {
            add(root,e);
        }
    }


    //向以node为根的为分搜索树中插入元素e，递归算法
    private void add(Node node,E e){
        if(e.equals(node.e)){
            return ;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size ++;
            return ;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size ++;
            return ;
        }

        //大于为正 小于为负
        if (e.compareTo(node.e) < 0) {
            add(node.left,e);  //如果左孩子不为空，递归插入到左子树中
        }else {
            add(node.right,e);
        }
    }


}
